package cn.itcast.algorithm.tree;

/**
 * 树的前序遍历、中序遍历、后序、层序遍历 递归实现
 * https://www.cnblogs.com/liuyang0/p/6271324.html
 * 前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。
 * 中序遍历:先遍历左子树，然后遍历根结点，最后遍历右子树。
 * 后序遍历:先遍历左子树，然后遍历右子树，最后遍历根节点。
 * 层序遍历：逐层遍历。
 * create by zhangtian3 on 2019/1/4
 */
public class TreeSearchSelf<AnyType extends Comparable<? super AnyType>> {
    /**
     * 定义了一个二叉树的结构
     * @param <AnyType>
     */
    private static class BinaryNode<AnyType> {
        AnyType element ;
        BinaryNode<AnyType> left ;
        BinaryNode<AnyType> right ;

        BinaryNode(AnyType theElement) {
            this(theElement, null ,null) ;
        }

        BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
            this.element = theElement ;
            this.left = lt ;
            this.right = rt ;
        }
    }

    private BinaryNode<AnyType> root ;// 树的根节点

    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if(t == null){
            return new BinaryNode<>(x, null ,null) ;
        }

        int compareResult = x.compareTo(t.element) ;
        if(compareResult < 0){
            t.left = insert(x, t.left) ;
        }

        return null ;
    }

}
